package backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 51.N皇后
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
public class solveNQueens {
    List<List<String>> res = new ArrayList<>();
    int[][] map;

    public List<List<String>> solveNQueens(int n) {
        map = new int[n][n];
        backtracking(0, n);
        return res;
    }

    public void backtracking(int flow, int n) {
        //if (x < 0 || x >= n || y < 0 || y >= n) return;
        if (flow == n) {
            List<String> path = new ArrayList<>();
            for (int i = 0; i < map.length; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < map[0].length; j++) {
                    if (map[i][j] == 1) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }

                }
                path.add(sb.toString());
            }
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (check(flow, i, n)) {
                map[flow][i] = 1;
                backtracking(flow + 1, n);
                map[flow][i] = 0;
            }
        }
    }

    public boolean check(int x, int y, int n) {
        for (int i = 0; i < n; i++) {
            if (map[x][i] == 1) {
                return false;
            }
        }
        for (int j = 0; j < n; j++) {
            if (map[j][y] == 1) {
                return false;
            }
        }
        for (int i = 0; i < n; i++) {
            if (x + i < n && y + i < n && map[x + i][y + i] == 1) {
                return false;
            } else if (x + i < n && y - i >= 0 && map[x + i][y - i] == 1) {
                return false;
            } else if (x - i >= 0 && y + i < n && map[x - i][y + i] == 1) {
                return false;
            } else if (x - i >= 0 && y - i >= 0 && map[x - i][y - i] == 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        new solveNQueens().solveNQueens(4);
    }
}

/**
 * hot100一刷
 * hot100二刷
 */
class So {
    List<List<String>> res = new ArrayList<>();
    char[][] map;

    public List<List<String>> solveNQueens(int n) {
        map = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(map[i], '.');
        }
        backtracking(n, 0);
        return res;
    }

    public void backtracking(int n, int row) {
        if (row == n) {
            List<String> path = new ArrayList<>();
            for (int i = 0; i < map.length; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < map[0].length; j++) {
                    sb.append(map[i][j]);
                }
                path.add(sb.toString());
            }
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid(row, i, n, map)) {
                map[row][i] = 'Q';
                backtracking(n, row + 1);
                map[row][i] = '.';
            }
        }
    }
    private boolean isValid(int row, int col, int n, char[][] chess) {
        // 检查这一列
        for (int i = 0; i < row; i++)
            if (chess[i][col] == 'Q')
                return false;
        // 检查这一行
        for (int j = 0; j < col; j++)
            if (chess[row][j] == 'Q')
                return false;
        // 检查45度的方向
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            if (chess[i][j] == 'Q')
                return false;
        // 检查135度的方向
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++)
            if (chess[i][j] == 'Q')
                return false;
        return true;  // 成功!
    }
}

